#include <stdio.h>
#include <assert.h>
#include <getopt.h>
#include <unistd.h>
#include <sys/types.h>
#include <dirent.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
// #define DEBUG
typedef int bool;

struct Arg {
  bool show_pid;
  bool n_sort;
  bool version;
};

struct procInfo {
  int pid;
  // 始终注意指针的初始化和堆区情况！！！
  char name[64];
  struct procInfo* next;
  struct procInfo* child;
};
typedef struct procInfo procInfo;
typedef struct Arg Arg;

/* ========== externs ==========*/
void parse_arg(int, char*[], Arg*);


/* ========== utils ========== */
#define Assert(x) if(x) ;else {printf("\n"#x" not satisfied!\n");assert(0);}


void print(procInfo* head) {
  if (head==NULL) return;
  printf("%d---%s\n", head->pid, head->name);
  print(head->child);
  print(head->next);
}

/* ========== functions ===========*/
void parse_arg(int argc, char* argv[], Arg* arg) {
  arg->n_sort = false;
  arg->show_pid = false;
  arg->version = false;

  int opt = 0;
  int loptind = 0;
  int temp = 0;
  char pattern[] = "-pnV";
  static struct option longOpts[] = {
    {"show-pids", no_argument, NULL, 'p'}, 
    {"numeric-sort", no_argument, NULL, 'n'}, 
    {"version", no_argument, NULL, 'V'}, 
    {0, 0, 0, 0}
  };

  while ((opt=getopt_long(argc, argv, pattern, longOpts, &loptind)) != -1) {
    switch (opt) {
      case 0: assert(0);
      case 'p': arg->show_pid = true; break;
      case 'n': arg->n_sort = true; break; 
      case 'V': arg->version = true; break;
      default: assert(0);
    }
  }

  #ifdef DEBUG
  printf("V:%d, n:%d, p:%d\n", arg->version, arg->n_sort, arg->show_pid);
  #endif

  return;
}

procInfo* proc_tree (){
  
  int num_proc = 0;
  DIR* root = NULL;
  struct dirent* ent = NULL;
  root = opendir("/proc");
  while ((ent=readdir(root)) != NULL) {
    if (ent->d_type==4 && ent->d_name[0]>='0' && ent->d_name[0]<='9') num_proc++;
  }
  closedir(root);

  procInfo* procs = malloc(sizeof(procInfo)*num_proc);
  Assert(procs!=NULL);
  int index = 0;
  root = opendir("/proc");
  while ((ent=readdir(root)) != NULL) {
    if (ent->d_type==4 && ent->d_name[0]>='0' && ent->d_name[0]<='9') {
      procs[index].pid = atoi(ent->d_name);
      // procs[index].name = "\0";
      procs[index].next = NULL;
      procs[index].child = NULL;
      index++;
    }
  }
  closedir(root);
  Assert(index==num_proc);

  // // insertion sort of pids
  // for (int i=1; i<num_proc; i++) {
  //   procInfo temp = procs[i];
  //   int p = i-1;
  //   while (p>=0&&temp.pid<procs[p].pid) {
  //     procs[p+1] = procs[p];
  //     p--;
  //   }
  //   procs[p+1] = temp;
  // }

  // Assert(procs[0].pid==1);

#ifdef DEBUG
  for (int i=0; i<num_proc; i++) {
    printf("%d ", procs[i].pid);
  }
  printf("\n");
#endif


  char buf[1024];

  procInfo* HEAD = (procInfo*)malloc(sizeof(procInfo));
  HEAD->child = NULL;
  strcpy(HEAD->name, "idle");
  HEAD->next = NULL;
  HEAD->pid = 0;

  for (int i=0; i<num_proc; i++) {
    char name[128];
    sprintf(buf, "/proc/%d/status", procs[i].pid);
    FILE* fp = fopen(buf, "r");
    int ppid = 0, p = -1;
    bool name_set=false, ppid_set=false;

    // printf("processing %d\n", procs[i].pid);
    char line[1024];
    while ((fgets(line, sizeof(line), fp))!=NULL) {
      // printf("the line is %s", line);
      if (strncmp(line, "Name:\t", 6)==0) {
        // printf("got name!\n");
        sscanf(line, "Name:\t%s\n", procs[i].name);
        name_set = true;
      }
      if (strncmp(line, "PPid:\t", 6)==0) {
        sscanf(line, "PPid:\t%d\n", &ppid);
        ppid_set = true;
      }
      if(ppid_set&&name_set) break;
    }


    // printf("name set to %s, ppid set to %d\n",procs[i].name, ppid);
    if (ppid==0) {
      procInfo* temp = HEAD->child;
      procs[i].next = temp;
      HEAD->child = &procs[i];
      continue;
    }
    else {
      for (p=0; p<num_proc; p++) {
        if (procs[p].pid==ppid) {
          procInfo* temp = procs[p].child;
          while (temp!=NULL&&temp->pid<i) temp = temp->next;
          procs[i].next = temp;
          procs[p].child = &procs[i];
          break;
        }
      }
    }
    // printf("p=%d\n", p);
    // Assert(p!=i);
    Assert(procs[i].name!=NULL)
  }

  return HEAD;
}

void show(procInfo* head, bool pid, int indent) {
  if (head==NULL) return;
  printf("\n");
  for (int i=0; i<indent; i++) printf(" ");
  printf("%s", head->name);
  if (pid) printf("(%d)", head->pid);
  show(head->child, pid, indent+4);
  show(head->next, pid, indent);
}

/* ========== main ==========*/
int main(int argc, char* argv[]) {
  Arg arg;
  parse_arg(argc, argv, &arg);

  if (arg.version) {
    fprintf(stderr, "pstree 1.0.0\n");
    fprintf(stderr, "Copyright (C) ChenX. Gao\n");
    fprintf(stderr, "\nThis is free software, and you are welcome to redistribute it under the terms of the MIT License.\n");
    fprintf(stderr, "For more information about these matters, see the web page github.com/Derek-Gcx.\n");
    return (0);
  }

  procInfo* head = proc_tree();
#ifdef DEBUG
  print(head);
#endif
  show(head, arg.show_pid, 0);
  return 0;
}